class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}
class BinarySearchTree {
  constructor() {
    this.root = null
  }
  // 二叉树的插入功能
  insertNode (node, newNode) {
    // insertNode方法的实现
    // 当传入的根节点没有子节点时 直接判断大小并插入
    // 如果左节点或右子节点有值，则递归调用，直到子节点为null时插入
    if (newNode.key.id < node.key.id) {
      // 情况1.小于则插入到左子树中
      if (node.left == null) {
        // 如果左子树为空，则直接插入
        node.left = newNode
      } else {
        // 如果左子树有值，则递归调用insertNode函数，直到left为空时插入
        this.insertNode(node.left, newNode)
      }
    }
    else {
      // 情况2.传入的节点大于node节点
      if (node.right === null) {
        // 2.1判断右子树是否为空，如果为空则直接插入
        node.right = newNode
      } else {
        // 2.2如果不为空则递归调用，直到右子树为空则插入
        this.insertNode(node.right, newNode)
      }
    }
  }
  insert (key) {
    // 1.先创建节点
    let newNode = new Node(key)
    // 2.判断添加的是否为根节点
    if (this.root === null) {
      // 2.1.当根节点不存在时
      this.root = newNode
    } else {
      // 2.2.当根节点存在时
      this.insertNode(this.root, newNode)
    }
  }
  // 二叉树的删除功能，删除功能分为多种情况去讨论
  /*
    1.删除的是叶子节点，直接删除即可
    2.删除的节点只有一个叶子节点，那么也可以删除 更改指向就可以
    3.删除的节点具有两个叶子节点
  */
  removeNode (id) {
    let curNode = this.root
    let parentNode = null
    // 1.先找到要删除的节点
    while (curNode.key.id != id) {
      parentNode = curNode
      if (id < curNode.key.id) {
        curNode = curNode.left
      } else {
        curNode = curNode.right
      }
      if (curNode === null) {
        return false
      }
    }
    // 删除情况分三种
    // 1.删除的节点没有子节点 1.1没有子节点也分为是否是根节点两种情况
    if (curNode.left === null && curNode.right === null) {
      // 判断当前是不是只有一个根节点
      if (curNode === this.root) {
        this.root = null
      }
      else {
        if (parentNode.left === curNode) {
          console.log(`${parentNode.key.content}的左节点是待删除节点`)
          parentNode.left = null
        }
        else {
          console.log(`${parentNode.key.content}的右节点是待删除节点`)
          parentNode.right = null
        }
      }
    }
    // 2.删除的节点有一个子节点 2.1子节点可能为left也可能为right
    else if (curNode.left === null || curNode.right === null) {
      if (curNode.left === null) {
        // 确定是父节点的左节点还是右节点
        if (parentNode.left === curNode) {
          parentNode.left = curNode.right
          curNode.right = null
        } else {
          parentNode.right = curNode.right
          curNode.right = null
        }
      } else {
        if (parentNode.left === curNode) {
          parentNode.left = curNode.left
          curNode.left = null
        } else {
          parentNode.right = curNode.left
          curNode.left = null
        }
      }
    }
    // // 两个节点都不为空的情况
    else {
      // 需要我们判断当前节点是父节点的左还是右
      if (parentNode.right === curNode) {

        parentNode.right = this.targetNode(curNode)


        console.log('当前节点是parent的右子树,删除成功')
      }
      else {
        parentNode.left = this.targetNode(curNode)
      }

    }
    // console.log(parentNode, curNode)
    return curNode
  }
  removeNodes (id) {
    if (!id) return null
    let curNode = this.root
    let preNode = null
    // 先找到待删除的节点
    while (curNode) {
      if (curNode.key.id === id) {
        console.log('找到了')
        break
      }
      preNode = curNode
      // 判断是左子树还是右子树
      if (curNode.key.id > id) {
        curNode = curNode.left
      }
      else {
        curNode = curNode.right
      }
    }
    // preNode为空则说明当前传入的node节点就是待删除节点
    if (!preNode) {
      return this.targetNode(curNode)
    }
    if (preNode.left && preNode.left.key.id === id) {
      preNode.left = this.targetNode(curNode)
    }
    if (preNode.right && preNode.right.key.id === id) {
      preNode.right = this.targetNode(curNode)
    }
    return this.root
  }
  // 封装一个后续节点的方法，这里方便我们删除使用
  targetNode (target) {
    // 如果没有传递，则返回null
    if (!target) return target
    // 如果没有右子树，则直接返回左子树
    if (!target.right) return target.left
    let cur = target.right
    // 找到右子树最左侧的
    while (cur.left) {
      cur = cur.left
    }
    // 将右子树中最小的left指向target的left
    cur.left = target.left
    return target.right
  }
  // 中序遍历
  middleTraverse () {
    // console.log(this.root)
    // 使用闭包来保存数据
    const middleData = []
    const dfs = function (root) {
      if (root === null) {
        return
      }
      // console.dir(`当前节点不为空，${root.key.id}`)
      dfs(root.left)
      middleData.push(root.key)
      dfs(root.right)
    }
    dfs(this.root)
    // console.log(middleData)
    return middleData
  }
  // 先序遍历
  preTraverse () {
    // 使用闭包来进行数据的存储
    const preData = []
    const dfs = function (root) {
      if (root === null) {
        // 节点为空则返回
        return
      }
      preData.push(root.key)
      dfs(root.left)
      dfs(root.right)
    }
    dfs(this.root)
    return preData
  }
  // 后序遍历
  lastTraverse () {
    const lastData = []
    const dfs = function (root) {
      if (root === null) {
        return
      }
      dfs(root.left)
      dfs(root.right)
      lastData.push(root.key)
    }
    dfs(this.root)
    return lastData
  }
  // 层序遍历
  sequenceTraverse () {
    const res = [], tempQueue = []
    if (this.root === null) return res
    tempQueue.push(this.root)
    while (tempQueue.length != 0) {
      let curValue = []
      let stop = tempQueue.length
      for (let i = 0; i < stop; i++) {
        let node = tempQueue.shift()
        curValue.push(node.key)
        // 存放下一层节点

        node.left && tempQueue.push(node.left)
        node.right && tempQueue.push(node.right)
      }
      res.push(curValue)
    }
    return res
  }
  // 反转二叉树
  reverseTree () {
    let root = this.root
    const reverT = function (root) {
      if (!root) return null
      const right = root.right
      root.right = reverT(root.left)
      root.left = reverT(right)
      return root
    }
    let res = reverT(root)
    return res
  }
  // 返回树中的最大值
  maxInTree () {
    if (this.root == null) {
      return null
    }
    let root = this.root
    while (root.right !== null) {
      root = root.right
    }
    return root.key
  }
  // 返回树中的最小值
  minInTree () {
    if (this.root == null) {
      return
    }
    let root = this.root
    while (root.left !== null) {
      root = root.left
    }
    return root.key
  }
  //返回树的节点个数
  sizeofTree () {
    return this.middleTraverse().length
  }
  // 根据id判断该节点是否在树中
  nodeInTree (id) {
    let node = this.root
    // 当节点不为空就一直循环
    while (node !== null) {
      // 如果id小于key.id则向左数中进行查找
      if (id < node.key.id) {
        node = node.left
      }
      else if (id > node.key.id) {
        node = node.right
      }
      else {
        console.log('找到了', node.key.content)
        return true
      }
    }
    return false
  }
}
let tree = new BinarySearchTree()

const treeData = [
  { id: 5, content: 'M' },
  { id: 3, content: 'A' },
  { id: 4, content: 'F' },
  { id: 7, content: 'B' },
  { id: 1, content: 'N' },
  { id: 2, content: 'L' },
  { id: 6, content: 'G' },
  { id: 9, content: 'K' },
  { id: 8, content: 'C' }
]
// 先将数据插入
treeData.forEach(item => {
  tree.insert(item)
})

let preRes = tree.preTraverse().map(item => {
  return `${item.id}${item.content}`
})
let middRes = tree.middleTraverse().map(item => {
  return `${item.id}${item.content}`
})
let lastRes = tree.lastTraverse().map(item => {
  return `${item.id}${item.content}`
})
console.log(tree)
console.log('先序遍历', preRes.join('->'))
console.log('中序遍历', middRes.join('->'))
console.log('后序遍历', lastRes.join('->'))
console.log('层序遍历', tree.sequenceTraverse())
console.log('树中的最大值节点为', tree.maxInTree())
console.log('树中的最小值节点为', tree.minInTree())
// console.log('反转二叉树', tree.reverseTree())
console.log(tree.nodeInTree(2))
console.log(tree.removeNodes(7))
// console.log('层序遍历', tree.sequenceTraverse())
console.log(tree)
